package leetcode.medium.limit50;

import java.util.ArrayList;
import java.util.List;

/**
 * @author yaoyao1.liu@zhaopin.com.cn
 * @since 2022-11-08 15:59
 **/
public class No22 {

    public static void main(String[] args) {


        No22 no22 = new No22();
        List<String> list = no22.generateParenthesis(3);
        System.out.println(list);
    }

    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        generateAll(new char[2 * n], 0, list);
        return list;
    }

    public void generateAll(char[] chars, int index, List<String> result) {
        if (index == chars.length) {
            if (valid(chars)) {
                result.add(new String(chars));
            }
        } else {
            chars[index] = '(';
            generateAll(chars, index + 1, result);
            chars[index] = ')';
            generateAll(chars, index + 1, result);
        }

    }

    public boolean valid(char[] chars) {
        int a = 0;

        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '(') {
                ++a;
            } else {
                --a;
            }
            if (a < 0) {
                return false;
            }
        }
        return a == 0;
    }
}
